package pl.poznan.put.cs.to.tsp.heuristics;

import java.util.LinkedList;
import java.util.Random;

import pl.poznan.put.cs.to.tsp.common.IResultHolder;
import pl.poznan.put.cs.to.tsp.common.Vertexes;
import pl.poznan.put.cs.to.tsp.listeners.TSPListener;

public class NormalHeuristic implements IResultHolder {

	private int countA;
	private int countB;
	private LinkedList<Integer> listA;
	private LinkedList<Integer> listB;
	private Random random;
	private boolean[] setA;
	private boolean[] setB;
	private int startA;
	private int startB;
	private boolean[] unattached;
	private Vertexes vertexes;
	private TSPListener tspListener;

	public NormalHeuristic(Vertexes vertexes, TSPListener tspListener) {
		this.vertexes = vertexes;
		this.random = new Random();
		this.tspListener = tspListener;
		this.generateResult();
	}

	private final int calculateDelta(boolean[] set, int index) {
		int result = 0;
		for (int i = 0; i < set.length; i++) {
			if (i != index && set[i]) {
				result += vertexes.getDistanceBetween(i, index);
			}
		}
		return result;
	}

	private int calculateLength(LinkedList<Integer> res) {
		int distance = 0;
		int first = res.getFirst();
		int last = res.getLast();
		int before = -1;

		for (Integer i : res) {
			if (before == -1) {
				distance += vertexes.getDistanceBetween(first, last);
			} else {
				distance += vertexes.getDistanceBetween(before, i);
			}
			before = i;
		}

		return distance;
	}

	private final int drawVertex() {
		return this.random.nextInt(vertexes.getNumberOfNodes());
	}

	private final LinkedList<Integer> generatePath(boolean[] set) {
		LinkedList<Integer> result = new LinkedList<Integer>();

		boolean[] s = set.clone();

		int count = 0;
		for (int i = 0; i < s.length; i++) {
			if (s[i]) {
				count++;
			}
		}

		int startIndex = this.random.nextInt(count);

		int k = 0;
		do {
			if (s[k]) {
				startIndex--;
			}
			k++;
		} while (startIndex >= 0);
		k--;

		int processed = 1;
		result.addLast(k);
		s[k] = false;

		while (processed < count) {
			int index = -1;
			int dist = Integer.MAX_VALUE;
			int last = result.getLast();
			for (int i = 0; i < s.length; i++) {
				if (s[i] && vertexes.getDistanceBetween(last, i) < dist) {
					index = i;
					dist = vertexes.getDistanceBetween(last, i);
				}
			}
			result.addLast(index);
			s[index] = false;
			processed++;
		}

		return result;
	}

	private final void generateResult() {
		this.unattached = new boolean[this.vertexes.getNumberOfNodes()];
		this.setA = new boolean[this.vertexes.getNumberOfNodes()];
		this.setB = new boolean[this.vertexes.getNumberOfNodes()];
		for (int i = 0; i < this.vertexes.getNumberOfNodes(); i++) {
			this.unattached[i] = true;
		}

		this.listA = new LinkedList<Integer>();
		this.listB = new LinkedList<Integer>();

		this.startA = this.drawVertex();
		do {
			this.startB = this.drawVertex();
		} while (this.startB == this.startA);

		this.unattached[this.startA] = false;
		this.unattached[this.startB] = false;
		this.setA[this.startA] = true;
		this.setB[this.startB] = true;

		this.countA = 1;
		this.countB = 1;
		int distA = 0;
		int distB = 0;
		int distBetween = 2 * vertexes.getDistanceBetween(this.startA,
				this.startB);
		double rateA = 0;
		double rateB = 0;

		while ((this.countA + this.countB) < this.vertexes.getNumberOfNodes()) {
			int bestIndex = -1;

			int deltaA = Integer.MAX_VALUE;
			int deltaB = Integer.MAX_VALUE;

			double afterRateA = Double.MAX_VALUE;
			double afterRateB = Double.MAX_VALUE;

			double deltaRate = Double.MAX_VALUE;

			for (int i = 0; i < this.vertexes.getNumberOfNodes(); i++) {
				if (this.unattached[i]) {
					int tempDeltaA = this.calculateDelta(this.setA, i);
					int tempDeltaB = this.calculateDelta(this.setB, i);

					double tempRateAA = ((double) distA + (double) tempDeltaA)
							/ (double) this.countA
							/ ((double) distBetween + (double) tempDeltaB)
							* (double) this.countB;
					double tempRateBA = 0;
					if (this.countB != 1) {
						tempRateBA = ((double) distB)
								/ ((double) this.countB - 1)
								/ ((double) distBetween + (double) tempDeltaA)
								* (double) this.countA;
					}

					double tempRateAB = 0;
					if (this.countA != 1) {
						tempRateAB = ((double) distA)
								/ ((double) this.countA - 1)
								/ ((double) distBetween + (double) tempDeltaB)
								* (double) this.countB;
					}
					double tempRateBB = ((double) distB + (double) tempDeltaB)
							/ (double) this.countB
							/ ((double) distBetween + (double) tempDeltaA)
							* (double) this.countA;

					double deltaRateA = (tempRateAA + tempRateBA)
							- (rateA + rateB);
					double deltaRateB = (tempRateAB + tempRateBB)
							- (rateA + rateB);

					// System.out.println("deltaRateA = " + deltaRateA
					// + ", deltaRateB = " + deltaRateB + ", deltaRate = "
					// + deltaRate);
					if (deltaRateA < deltaRateB) {

						if (deltaRateA < deltaRate) {
							// System.out.println("A");
							bestIndex = i;
							deltaA = tempDeltaA;
							deltaB = 0;
							afterRateA = tempRateAA;
							afterRateB = tempRateBA;
							deltaRate = deltaRateA;
						}
					} else {

						if (deltaRateB < deltaRate) {
							// System.out.println("B");
							bestIndex = i;
							deltaA = 0;
							deltaB = tempDeltaB;
							afterRateA = tempRateAB;
							afterRateB = tempRateBB;
							deltaRate = deltaRateB;
						}
					}
				}
			}

			if (deltaA == 0) { // wstawiamy do B
				this.setB[bestIndex] = true;
				this.unattached[bestIndex] = false;
				this.countB++;
				distB += deltaB;
				distBetween += deltaA;
				rateA = afterRateA;
				rateB = afterRateB;
			} else if (deltaB == 0) { // wstawiamy do A
				this.setA[bestIndex] = true;
				this.unattached[bestIndex] = false;
				this.countA++;
				distA += deltaA;
				distBetween += deltaB;
				rateA = afterRateA;
				rateB = afterRateB;
			}
		}
		this.listA = this.generatePath(this.setA);
		this.listB = this.generatePath(this.setB);
		this.tspListener.solutionGenerated(listA, listB, vertexes);
	}

	@Override
	public int getLengthA() {
		return calculateLength(this.listA);
	}

	@Override
	public int getLengthB() {
		return calculateLength(this.listB);
	}

	@Override
	public final LinkedList<Integer> getListA() {
		return this.listA;
	}

	@Override
	public final LinkedList<Integer> getListB() {
		return this.listB;
	}

	@Override
	public Vertexes getVertexes() {
		return vertexes;
	}

	private final void printResult(LinkedList<Integer> res) {
		for (Integer i : res) {
			System.out.print(i + " -> ");
		}
		System.out.println();
	}

	// public void printResults() {
	// System.out.println("SetA (" + this.countA + "):");
	// for (int i = 0; i < this.setA.length; i++) {
	// if (this.setA[i]) {
	// System.out.print(i + " ");
	// }
	// }
	// System.out.println();
	// System.out.println("SetB (" + this.countB + "):");
	// for (int i = 0; i < this.setB.length; i++) {
	// if (this.setB[i]) {
	// System.out.print(i + " ");
	// }
	// }
	// System.out.println();
	//
	// System.out.println("A: " + this.getLengthA());
	// this.printResult(listA);
	// System.out.println("B: " + this.getLengthB());
	// this.printResult(listB);
	// }
	
	@Override
	public int compareTo(IResultHolder o) {
		int local = this.getLengthA() + this.getLengthB();
		int other = o.getLengthA() + o.getLengthB();
		return local - other;
	}
}
